package edu.pw.elka.gtsna.graph_algorithms;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

import edu.pw.elka.gtsna.graph.Graph;



/**
 * 
 * Dijkstra Algorithm to compute shortest paths in a given graph and subgraph
 *
 */
public class Dijkstra {
	
	/* Graph */
	Graph graph;
	
	
    protected Integer distances[];
    
    protected Integer  predecessors[];
       
    protected Integer allDistances[][];
    
    
    public void setAllDistances(Integer[][] allDistances) {
		this.allDistances = allDistances;
	}

    
    public Dijkstra(Graph graph, Set<Integer> subgraph, Integer allDistances[][]){
    	this.graph = graph;
    	this.allDistances = allDistances;
    	distances = new Integer[graph.getNumOfNodes()+1];
    	predecessors = new Integer[graph.getNumOfNodes()+1];
    }
    
    public Dijkstra(Graph graph, Integer allDistances[][]){
    	this(graph,graph.getAllNodes(),allDistances);
    }
    
    protected Integer dist(int a, int b){
    	return (int) allDistances[a][b];
    }
    
    /**
     * Compute distance from source to sink
     * @param source
     * @param sink
     */
	 public void computePaths(Integer source, Integer sink) {
		// System.out.println("Dijkstra: "+source+"->"+sink);
	    	distances = new Integer[graph.getNumOfNodes()+1];
	    	predecessors = new Integer[graph.getNumOfNodes()+1];
		 
		for(int v: graph.getAllNodes())
			distances[v] = Integer.MAX_VALUE;
		 
		 distances[source] = 0;
		 predecessors[source] = null;

        PriorityQueue<Integer> vertexQueue = new PriorityQueue<Integer>(graph.getNumOfNodes(), new VerticesComparator());
        for(int v: graph.getAllNodes())
        	vertexQueue.add(v);
	
        
		while (!vertexQueue.isEmpty()) {
		   Integer u = vertexQueue.poll();
		   if (u == sink)
			   break;
	            // Visit each edge exiting u
           for(Integer v: graph.getNeigbours(u))
            {   
				if (distances[u] < distances[v] - dist(u,v)) {
				    vertexQueue.remove(v);
				    distances[v] = distances[u] + dist(u,v);
				    predecessors[v]= u;
				    vertexQueue.add(v);
				}
            }
	    }
	 }
	  
	  public List<Integer> getShortestPathTo(Integer sink) {
	        List<Integer> path = new ArrayList<Integer>();
	        for (Integer vertex = sink; vertex != null; vertex = predecessors[vertex]){
	            path.add(vertex);
	        }
	        Collections.reverse(path);
	        return path;
	   }
	   
	 
	 public class VerticesComparator implements Comparator<Integer>
	 {
	     @Override
	     public int compare(Integer x, Integer y)
	     {
	         if (distances[x] < distances[y])
	         {
	             return -1;
	         }
	         if (distances[x] > distances[y])
	         {
	             return 1;
	         }
	         return 0;
	     }
	 }
	 
}
